package cn.edu.jxau.test;

import java.util.ArrayList;
import java.util.List;
import java.util.Objects;

/**
 * 基于无序链表的无序符号表
 * put：O(1)
 * get：O(n)
 * 
 * @author 付大石
 */
public class LinkedListST<K,V> {
    
    public static void main(String[] args) {
        
        LinkedListST<Character,Integer> st = new LinkedListST<Character, Integer>();
        st.put('S',0);
        st.put('E',1);
        st.put('A',2);
        st.put('R',3);
        st.put('C',4);
        st.put('H',5);
        st.put('E',6);
        st.put('X',7);
        st.put('A',8);
        st.put('M',9);
        st.put('P',10);
        st.put('L',11);
        st.put('E',12);
        for(Character item : st.keys()) {
            System.out.println(item+"   "+st.get(item));
        }
        System.out.println(st.contains('A'));
        System.out.println(st.contains('B'));
        System.out.println(st.contains('C'));
        System.out.println(st.size());
        
    }
    
    /**
     * 链表头结点
     */
    private Node first;
    
    /**
     * 链表中元素个数
     */
    private int size;
    
    
    public LinkedListST() {
        
        first = new Node(); //空头结点
    }
    
    public void put(K key,V value) {
        
        // 参数校验 //
        Objects.requireNonNull(key, "参数key不能为null");
        if(value == null) {
            delete(key);
			return ;
        }
        
        // 修改链表 //
        Node cursor = first.next;
        while(cursor != null) {
            if(cursor.key.equals(key)) { //键值对已经存在于链表中
                cursor.value = value;
                return ;
            }
            cursor = cursor.next;
        }
        Node node = new Node(key,value); // 循环结束，键值对不存在于链表中，插入一个键值对结点
        node.next = first.next;
        first.next = node;
        size++;
    }
    
    public V get(K key) {
        
        Objects.requireNonNull(key, "参数key不能为null");
        Node cursor = first.next;
        while(cursor != null) {
            if(cursor.key.equals(key)) { // 键值对匹配
                return cursor.value;
            }
            cursor = cursor.next;
        }
        return null;
    }
    
    public void delete(K key) {
        
        Objects.requireNonNull(key, "参数key不能为null");
        Node cursor = first;
        while(cursor.next != null) {
            if(cursor.next.key.equals(key)) {
                cursor.next = cursor.next.next;
                size--;
                return ;
            }
            cursor = cursor.next;
        }
    }
    
    public boolean contains(K key) {
        
        Objects.requireNonNull(key, "参数key不能为null");
        Node cursor = first.next;
        while(cursor != null) {
            if(cursor.key.equals(key)) {
                return true;
            }
            cursor = cursor.next;
        }
        return false;
    }
    
    public int size() {
        return size;
    }
    
    public Iterable<K> keys() {
        
        List<K> list = new ArrayList<>();
        Node cursor = first.next;
        while(cursor != null) {
            list.add(cursor.key);
            cursor = cursor.next;
        }
        return list;
    }
    
    private class Node {
        
        private K key;
        private V value;
        private Node next;
        
        public Node() {
            
        }
        
        public Node(K key,V value) {
            this.key = key;
            this.value = value;
        }
    }
}
